Presently, raster scan printers are called upon to produce binary level pixel half-tone images from grey level pixel images. In a grey level pixel image, each pixel element fed from a processor includes a multi-bit value that defines the pixel's grey level. An 8-bit byte can define any of 0-255 grey levels. In converting such a grey level pixel image to a binary level pixel image, each pixel's grey level value is compared to a threshold and, if the grey level value exceeds or equals the threshold, it is assigned a first binary value (e.g. a 1). If its value is less than the threshold, it is assigned a complementary binary value (e.g. a 0). Such conversion accomplishes the creation of a binary half-tone image.
The quality of the image that is created suffers as a result of the conversion processing not taking into account error values that occur during the conversion process. An "error value" is the difference between the binary pixel value after conversion and the grey level value of the pixel before conversion.
To improve the quality of binary pixel images, Floyd et al. in "An Adaptive Algorithm Spatial Grey Scale", Proceedings of the Society for Information Display, Volume 17, No. 75 (1976), pp. 36-37, suggest that error values be diffused to adjacent pixels so as to provide smoother half-tone transitions. Floyd et al. allocate defined fractions of the error value to plural adjacent pixels on both a same scan line and on a next scan line, respectively. Such action requires that substantial amounts of memory be allocated for the storage of the scan line error values so that the allocation can be accomplished as a next scan line of pixel values is encountered.
Various techniques have been developed to reduce the memory accesses required to accomplish the Floyd et al. error diffusion procedure. For instance, see U.S. Pat. No. 5,337,160 to Jones, assigned to the same assignee as this application.
The above-described error-diffusion procedure, as well as many others, are referred to as dither procedures. The most simple dither procedure is where an 8-bit grey level value is compared to a fixed threshold value, as described above, and the output of the comparison action results in either a 1 or 0 being generated that causes either a dot to be printed or no dot to be printed. The use of a constant threshold works well with text and certain types of half-tone images, but does not work well with continuous tone image scans. A further type of dither, termed "ordered" dither, causes an 8-bit grey value to be compared to a number from a table of values that is based on a row and column position of the pixel in the image. The table values (i.e. threshold levels) is used to form a "super pixel" or larger dot that is periodically spaced on a page, with the size of the dot related to the grey scale value. Ordered dither works well with continuous tone data images, has some moire problems with half-tone images, and tends to make text scans look jagged.
A random dither derives threshold numbers from a random number generator, and employs such random numbers as threshold values at successive pixel positions. Such random dither is also known as white noise dither and results in a spattering of small dots on the page. The density of the dots is related to the grey level value of the grey level pixel values. White noise dither adds graininess to text, half-tone and continuous tone scans.
There is also a type of dither known as blue noise dither which combines a white noise thresholding -comparison operation at each pixel with a propagation of error values at each pixel position to adjoining pixels. Such a blue noise dither error diffusion procedure requires errors from at least one full scan line of grey level pixel data to be stored, pending receipt of a next full scan line of pixel data.
In a blue noise dither procedure, if error values are propagated only to the "right" of each individual pixel in a scan line (and not to pixels in a next scan line), that the resulting error values cause "streaks" in the image. This is due to the fact that the previous scan line does not convey to the subsequent scan line where the error lies therein. Accordingly, the next scan line can have similar error values which line up in the same places in the image, thus causing streaking. The benefit of propagating error values only to the right in a scan line is that only one pixel error value at a time needs be stored and memory requirements are greatly reduced. However, as aforesaid, the pixel image suffers significantly.
Accordingly, it is an object of this invention to employ an improved dither procedure wherein error value memory requirements are minimized.
It is another object of this invention to provide an improved method and apparatus for conversion of a grey level pixel image to a binary level pixel image, wherein an improved dither procedure is employed that avoids the imposition of patterns on the resulting image.